#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

double findKth(int a[], int m, int b[], int n, int k)
{
    if (m > n) return findKth(b, n, a, m, k);

    if (m == 0) return b[k-1];
    if (k == 1) return min(a[0], b[0]);
    int pa = min(k/2, m), pb = k - pa;
    if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
    return findKth(a, m, b+pb, n-pb, k-pb);
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m+n;
    if (total&0x1) 
        return findKth(A, m, B, n, total/2+1);
    else 
        return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total/2+1))/2;
}
                                


int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;
    int B[] = {1,3,4,5,6,8};
    int A[] = {2,4,7,9};
    cout << findMedianSortedArrays(A, sizeof(A)/sizeof(int), B, sizeof(B)/sizeof(int)) << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
